package _0517_Super_Washing_Machines;

/**
 * Date: 2021/9/29 10:19
 * Content:执行用时：1 ms, 在所有 Java 提交中击败了87.24%的用户
 * 内存消耗：39.2 MB, 在所有 Java 提交中击败了5.10%的用户
 */
public class Solution {

    public int findMinMoves(int[] w) {
        int s = 0, n = w.length;
        for (int x : w) s += x;
        if (s % n != 0) return -1;

        int avg = s / n, left = 0, right = s;
        int res = 0;
        for (int i = 0; i < n; i++) {
            right -= w[i];
            if (i != 0) left += w[i - 1];
            int l = Math.max(avg * i - left, 0);  // 左边缺少的衣服数量
            int r = Math.max(avg * (n - i - 1) - right, 0);  // 右边缺少的衣服数量
            res = Math.max(res, l + r);
        }
        return res;
    }

    public static void main(String[] args) {

        int[] w = {0, 0, 6, 6};
        System.out.println((new Solution()).findMinMoves(w));  // 6
    }
}
